题目分析

本题难度并不大，但是一定要认真思考，明白题目究竟想干什么，考虑清楚时间复杂度然后再去敲代码。

数学

假设用0和1表示开关的状态，1表示打开了，0表示关闭了。

我们先思考这四个开关，假设有10个灯泡，我们模拟一下

反转所有开关，即1 1 1 1 1 1 1 1 1 1 -> 0 0 0 0 0 0 0 0 0 0
反转偶数开关，即1 1 1 1 1 1 1 1 1 1 -> 0 1 0 1 0 1 0 1 0 1
反转奇数开关，即1 1 1 1 1 1 1 1 1 1 -> 1 0 1 0 1 0 1 0 1 0
反转指定开关，即1 1 1 1 1 1 1 1 1 1 -> 1 0 0 1 0 0 1 0 0 1

我们可以发现什么规律，是不是以6为周期的，因为开关1是以1为周期，k1[i] = k1[i + 1]，同理开关2和3是以2为周期，开关4是以3为周期。因此最小公倍数是6，所以无论无何按下按钮，k[n] = k[n + 6]。

所以如果灯泡大于6个，我们可以把灯泡范围缩小到6。

我们继续观察如果只有6个开关，那么灯泡2和灯泡6是否相同，因为开关4只涉及1和4，因此其他三个开关，无论如何按，灯泡2和灯泡6一定是同时变化的。同理灯泡3和5也是一样。

所以进一步我们可以将灯泡的范围缩小到4个。

下面我们看操作次数，我们记操作开关1为A，开关2为B，开关3为C，开关4为D。

那么我们发现A = BC、B = AC、C = AB、DD = AA = BB = CC = NULL

所以出现的可能性最多只有A、B、C、D、AA、AD、BD、CD，再多任何一种都可以用上面的表达，这个很简单，排列组合即可。所以我们只需要两次操作即可。

但是有一种情况需要考虑，就是D单独出现的情况，如果操作次数是2，是无法出现D这个选项的，因为A可以用BC两次操作替代、B可以用AC替代、C可以用AB替代，但是D不行，如果必须要操作两次，D则无法出现。因此我们至少需要操作3次。

操作3次就可以出现上述8种可能，A、B、C、D可以看作A+AA、B+AA、C+AA、D+AA。AA可以看作A+BC、AD可以看作BC+D、BD可以看作AC+D、CD可以看作AB+D。

也不会存在超过3次，但是不出现8种可能的情况，假设press为m

因为如果D为奇数，那么可以将两个D消去，变成NULL，按下一个D，然后其他的情况就是用ABC中的任意两个表示。

如果D为偶数，那么最后一定没有D，其他情况就是用ABC中的任意三个表示。

所以本题深搜3层即可覆盖所有的情况。

所以可以将本题的范围改为n = Math.min(n, 4)，一共最多有4个灯泡，press = Math.min(press, 3)。然后用一个Set表示灯泡的状态即可。

算法的**时间复杂度为O(1)，空间复杂度为O(1)**。

class Solution {
    public int flipLights(int n, int presses) {
        n = Math.min(n, 4);
        int[] states = new int[]{0b1111 >> (4 - n), 0b1010 >> (4 - n), 0b0101 >> (4 - n), 0b1001 >> (4 - n)};
        presses = Math.min(presses, 3);
        HashSet<Integer> res = new HashSet<>();
        dfs(presses, 0, states, res);
        return res.size();
    }

    private void dfs(int layer, int cur, int[] states, HashSet<Integer> res) {
        if (layer == 0) {
            res.add(cur);
            return;
        }
        dfs(layer - 1, cur ^ states[0], states, res);
        dfs(layer - 1, cur ^ states[1], states, res);
        dfs(layer - 1, cur ^ states[2], states, res);
        dfs(layer - 1, cur ^ states[3], states, res);
    }
}

刷题总结

代码非常简单，重要的是如何能把复杂的问题抽象出简单的数学逻辑。当然如果是面试或者是竞赛，小伙伴们也不一定要推导的这么详细，如果能够将n压缩到6，press压缩到3，并能解释清楚为什么大于3次的都能用3表示，基本上面试和竞赛都能通过啦。